|
In mathematical logic, the Löwenheim–Skolem theorem, named for Leopold Löwenheim and Thoralf Skolem, states that if a countable first-order theory has an infinite model, then for every infinite cardinal number κ it has a model of size κ. The result implies that first-order theories are unable to control the cardinality of their infinite models, and that no first-order theory with an infinite model can have a unique model up to isomorphism. The (downward) Löwenheim–Skolem theorem is one of the two key properties, along with the compactness theorem, that are used in Lindström's theorem to characterize first-order logic. In general, the Löwenheim–Skolem theorem does not hold in stronger logics such as second-order logic. == Background == A signature consists of a set of function symbols ''S''func, a set of relation symbols ''S''rel, and a function representing the arity of function and relation symbols. (A nullary function symbol is called a constant symbol.) In the context of first-order logic, a signature is sometimes called a language. It is called countable if the set of function and relation symbols in it is countable, and in general the cardinality of a signature is the cardinality of the set of all the symbols it contains. A first-order theory consists of a fixed signature and a fixed set of sentences (formulas with no free variables) in that signature. Theories are often specified by giving a list of axioms that generate the theory, or by giving a structure and taking the theory to consist of the sentences satisfied by the structure. Given a signature σ, a σ-structure ''M'' is a concrete interpretation of the symbols in σ. It consists of an underlying set (often also denoted by "''M''") together with an interpretation of the function and relation symbols of σ. An interpretation of a constant symbol of σ in ''M'' is simply an element of ''M''. More generally, an interpretation of an ''n''-ary function symbol ''f'' is a function from ''M''''n'' to ''M''. Similarly, an interpretation of a relation symbol ''R'' is an ''n''-ary relation on ''M'', i.e. a subset of ''M''''n''. A substructure of a σ-structure ''M'' is obtained by taking a subset ''N'' of ''M'' which is closed under the interpretations of all the function symbols in σ (hence includes the interpretations of all constant symbols in σ), and then restricting the interpretations of the relation symbols to ''N''. An elementary substructure is a very special case of this; in particular an elementary substructure satisfies exactly the same first-order sentences as the original structure (its elementary extension). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Löwenheim–Skolem theorem」の詳細全文を読む スポンサード リンク
|